#include "./sa_solver.h"
#include "./common.h"
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;

SA_Solver::SA_Solver(std::vector<Cube> &cubes) : Simulated_Annealing(cubes) {
	// Initialize the coefficient
	srand(time(0));
	n_ = cubes.size();
	initial_possibility_ = 0.98;
	stop_eps_ = 1e-6;
	SetTimeLimitation(600);
}

void SA_Solver::SetTimeLimitation(int time_limitation) {
	time_limitation_ = time_limitation;
	temperature_drop_velocity_.assign(3, 0);
	// if the time is limited find an approximate solution
	if (time_limitation_  < 1000) {
		temperature_drop_velocity_[0] = 0.9;
		temperature_drop_velocity_[1] = 0.95;
		temperature_drop_velocity_[2] = 0.98;
		random_frequency_ = 1000000 / n_;
	} 
	// otherwise pursue the precise solution according to  the time limitaion
	else {
		time_limitation_ = min(time_limitation_, 1000000);
		temperature_drop_velocity_[0] = 0.93;
		temperature_drop_velocity_[1] = 0.96;
		temperature_drop_velocity_[2] = 0.98;
		random_frequency_ = time_limitation_ * 1000 / n_;
	}
	return ;
}

// Transform to another status and return the index of the operation 
int SA_Solver::Transform(TTree  & tree, vector<int> & t) { 
	// Choose three transform operation according to certain possibility
	transform_times_++;
	t.assign(3, 0);
	t[0] = n_ / 2;
	t[1] = 6;
	t[2] = n_;
	int opt = rand() % (t[0] + t[1] + t[2]);
	if (opt < t[0]) {  // swap the position of two cube
		int u = rand() % n_, v = rand() % n_;
		while (u == v) {
			u = rand() % n_;
			v = rand() % n_;
		}
		tree.SwapNode(u, v);
		return 0;
	}
	else if (opt < t[0] + t[1]) {  // rotate a cube
		int u = rand() % n_, k = rand() % 6;
		tree.ModifyCube(u, k);
		return 1;
	}
	else {  // move a set of cubes to another position
		vector<int> tmp_node;
		tmp_node.reserve(n_ * 3);
		int u = rand() % n_;
		Stack<int> s(n_);
		s.push(tree.root_);
		while (!s.empty()) {
			int cnt = 0, i = s.top(); s.pop();
			if (i == u) continue;
			for (int j = 1; j <= 3; ++j)
				if (tree.nodes_[i][j] != -1) {
					s.push(tree.nodes_[i][j]);
					}else ++cnt;
			if (!cnt) continue;
			tmp_node.push_back(i);
		}
		if (tmp_node.size() == 0) return -1;
 		int v = rand() % tmp_node.size();
		tree.MoveNode(u, tmp_node[v]);
		return 2;
	}
	return -1;
}

// get the solution and return the packed cubes
void SA_Solver::GetAns(std::vector<Cube> & cubes) { 
	int start_clock = clock();
	Average_Volume_ = 0; SA_times_ = 0;
	while ((clock() - start_clock) / CLOCKS_PER_SEC < time_limitation_) {
		SASolve(); 
		SA_times_++;
		Average_Volume_ += now_tree_.GetVolume();
		//cout << "The current fill ratio is " << (double) original_volume_ / now_tree_.GetVolume()  << ";  ";
		cout << "The best fill ratio is " << (double) original_volume_ / best_tree_.GetVolume()  << " so far." << endl;
	}
	Average_Volume_ /= SA_times_;
	//cout << "The Average fill ratio of " << tot << " rounds is " <<  (double) original_volume_ / Average_Volume << endl;
	best_tree_.GetPlacement(cubes);
	best_tree_.PrintTree();
	return ;
}